/*
 * @lc app=leetcode.cn id=433 lang=typescript
 *
 * [433] 最小基因变化
 */

// @lc code=start
interface UnitData {
  step: number;
  dna: string;
}

function minMutation(start: string, end: string, bank: string[]): number {
  const keys: string[] = ['A', 'C', 'G', 'T'];
  const bankSet = new Set<string>(bank);
  const visited = new Set<string>();

  if (start === end) return 0;
  if (!bankSet.has(end)) return -1;

  const queue: UnitData[] = [{ dna: start, step: 0 }];
  visited.add(start);
  while (queue.length) {
    const { dna, step } = queue.shift();
    if (dna === end) return step;
    for (let i = 0; i < 8; i++) {
      for (let k = 0; k < 4; k++) {
        if (dna[i] === keys[k]) continue;
        const str = [...dna];
        str[i] = keys[k];
        const next = str.join('');
        if (visited.has(next)) continue;
        if (!bankSet.has(next)) continue;
        queue.push({ dna: next, step: step + 1 });
        visited.add(next);
      }
    }
  }
  return -1;
}
// @lc code=end
